// 给定一个 没有重复 数字的序列，返回其所有可能的全排列。

function permute(nums: number[]): number[][] {
    // 安全校验
    if (nums.length < 1) {
        return [];
    }
    const res: number[][] = []; // 结果数组
    const isSelected: boolean[] = new Array(nums.length).fill(false);// 标记数组
    return permute_DFS(nums, res, [], isSelected);
};
// 深度优先遍历辅助方法
function permute_DFS(nums: number[], res: number[][], path: number[], isSelected: boolean[]): number[][] {
    // 递归出口
    if (path.length === nums.length) {
        res.push(Array.from(path));
        return res;
    }
    // 选择过程
    for (let i = 0; i < nums.length; i++) {
        if (!isSelected[i]) {// 如果当前的数字没有被选过才进行操作
            path.push(nums[i]);
            isSelected[i] = true;
            permute_DFS(nums, res, path, isSelected);// 在基础上继续深度优先搜索
            // 回溯算法部分,又叫状态重置
            path.pop();
            isSelected[i] = false;
        }
    }
    return res;
}

// 这道题目是一道非常经典的深度优先搜索结合回溯算法的例题
// 回溯算法采用试错的思想，它尝试分步的去解决一个问题。
// 在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，
// 它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。
// 回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
// 1.找到一个可能存在的正确的答案；
// 2.在尝试了所有可能的分步方法后宣告该问题没有答案。
// 落到这道题目上,首先我们在一个路径数组的状态下不断选择新的元素加入路径
// 这个选择过程就可以依靠深度优先搜索来实现
// 而对于不同的元素进行选择,只需要做一个循环即可
// 已经走到底的路径数组我们浅拷贝一个实例加入结果数组即可
// 这里我们又遇到一个问题,在这个简单用循环模拟选择的过程中,我们怎么知道当前元素是否已经被选中了?
// 自然的办法是可以引用一个标记数组(用布尔值描述),当我们选中一个元素时就把布尔值设立为true
// 之后一轮搜索结束,我们需要重置当前的状态,这个过程就要用到回溯算法
// 回溯的内容就是把搜索之前的全部操作撤销一遍
// 这样就完成了对这道题目代码的书写.


